/**
 * https://leetcode-cn.com/problems/minimum-path-sum/
 * 最小路径和
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
 * @param grid
 */
const minPathSum = (grid: number[][]): number => {
  // 行的长度
  const row = grid.length;

  // 列的长度
  const col = grid[0].length;

  // dp[i] 表示第x行第i列的最小路径和, 每次计算一行
  // dp[i] = min{dp[i], dp[i - 1]} + grid[i][j]
  const dp: number[] = new Array(col + 1).fill(0); // 初始化为最大, 方面初始化第一行

  // 初始化第一行
  for (let i = 1; i <= col; i++) {
    dp[i] = grid[0][i - 1] + dp[i - 1];
  }
  
  for (let i = 1; i < row; i++) {
    // 初始化第一列, 第一列为dp的第二项, 也就是开始项
    dp[0] = dp[1];
    for (let j = 1; j <= col; j++) {
      // 当前的最小值
      dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j - 1];
    }
  }

  return dp[col];
};

const minPathSum2 = (grid: number[][]): number => {
  // 行的长度
  const row = grid.length;

  // 列的长度
  const col = grid[0].length;

  // dp[i] 表示第x行第i列的最小路径和, 每次计算一行
  // dp[i] = min{dp[i], dp[i - 1]} + grid[i][j]
  const dp: number[] = new Array(col + 1).fill(Number.MAX_SAFE_INTEGER); // 初始化为最大, 方面初始化第一行

  dp[0] = 0; // 初始化wei 0
  for (let i = 0; i < row; i++) {
    // 初始化第一列, 如果不是第一行的的话
    i !== 0 && (dp[0] = Number.MAX_SAFE_INTEGER);
    for (let j = 1; j <= col; j++) {
      // 当前的最小值
      dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j - 1];
    }
  }

  return dp[col];
};

console.log(
  minPathSum([
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
  ])
);
console.log(
  minPathSum([[1,2,3],[4,5,6]])
);
console.log(
  minPathSum([[1, 2],[1, 1]])
);
console.log(
  minPathSum([
    [1, 2],
    [5, 6],
    [1, 1],
  ])
);
